package edu.bupt.e1btree;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class T10BinaryTreeZigzag {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        if (null == root) return res;

        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        int newcount = 0;
        int curcount = 1;
        boolean toRright = true;
        LinkedList<Integer> temp = new LinkedList<Integer>();
        while (queue.size() > 0){
            if (toRright){
                TreeNode cur = queue.removeFirst();
                temp.add(cur.val);
                curcount--;

                if (null != cur.left){
                    queue.addLast(cur.left);
                    newcount++;
                }
                if (null != cur.right){
                    queue.addLast(cur.right);
                    newcount++;
                }

            } else {
                TreeNode cur = queue.removeLast();
                temp.add(cur.val);
                curcount--;
                if (null !=cur.right){
                    queue.addFirst(cur.right);
                    newcount++;
                }
                if (null != cur.left){
                    queue.addFirst(cur.left);
                    newcount++;
                }
            }

            if (0==curcount){
                toRright = !toRright;
                curcount = newcount;
                newcount = 0;
                res.add(temp);
                temp = new LinkedList<Integer>();
            }
        }

        return res;
    }
}
